Field of the Invention
The present invention relates generally to decoding turbo codes and convolutional codes, and more particularly, to low complexity list decoding of turbo codes and convolutional codes.
Description of the Related Art
The turbo encoder/decoder is an important component in 3rd Generation Partnership Project (3GPP) High Speed Packet Access/Long Term Evolution (HSPA/LTE) modem chipsets. A 3GPP turbo code consists of two component convolutional codes. Each component convolutional code can be represented by a trellis. Current modem chipsets employ an iterative Scaled Maximum-Log MAP (SMLM) algorithm for turbo decoding, where MAP stands for the Maximum A Posteriori probability. The goal of iterative SMLM decoding is to achieve Maximum Likelihood (ML) estimation of information bits by iterations between two constituent decoders at medium to high Signal-to-Noise Ratio (SNR). After each half turbo decoding iteration, the output of each constituent decoder provides a single candidate convolutional codeword whose systematic part is used for Cyclic Redundancy Check (CRC) error detection. In this approach, the output of SMLM decoding is the ML codeword, and candidate codewords other than the most likely one of each constituent code are not explicitly identified or utilized.
The probability of a decoding error may be reduced by considering codewords other than the single most likely codeword. List turbo decoding generates a list of other very likely candidate codewords, besides the ML codeword. Hence, list decoding can decrease the decoder error probability, because the probability that all candidate codewords will fail may be significantly lower than that of the ML codeword. If an error free codeword exists in the list of candidate codewords, then it will be found via CRC error detection.
Conventional Maximum-Log MAP (MLM) decoding of a component convolutional code in one half turbo decoding iteration involves metric calculations at each trellis stage k, for each transition branch with incoming state s′ and outgoing state s, MLM recursively calculates the forward and backward state metrics and the path metrics as follows:αk(s)=EMBED Equation. 3max′s[αk−1(s′)+γz(s′,s)]βk−1(s)=maxs′[βk(s)+γk(s′,s)]σk′(s′,s)=αk−1(s′)+γk′(s′,s)+βk−1(s).
Based on the metric σk(s′, s) for the path with incoming state s′ and outgoing state σk(s′, s), MLM produces a Log Likelihood Ratio (LLR) for the k-th bit as
      Λ    k    =                    max                                            (                                                s                  ′                                ,                s                            )                        ⁢                                          u                k                            ⁡                              (                                                      s                    ′                                    ,                  s                                )                                              =          0                    ⁢                        σ          k                ⁡                  (                                    s              ′                        ,            s                    )                      -                  max                                            (                                                s                  ′                                ,                s                            )                        ⁢                                          u                k                            ⁡                              (                                                      s                    ′                                    ,                  s                                )                                              =          1                    ⁢                                    σ            k                    ⁡                      (                                          s                ′                            ,              s                        )                          .            
Taking the sign of the LLR of each information bit, the hard-decision vector which corresponds to the Maximum-Likelihood (ML) path of the component code is produced.
Maximum-Log List (MLL) decoding performs the same forward recursions for all αk(s) as the standard MLM algorithm. Then, based on the value of σk(s′, s) it ranks all path metrics available from the MLM algorithm along the backward recursion. It maintains a list of L candidate paths by the following record:
      R    ⁡          (      l      )        =            (                                    Metric                                                PreState                                                SuccState                                                TrellisStep                              )        =          (                                                                  σ                k                            ⁡                              (                                                      s                    ′                                    ,                  s                                )                                                                                        s              ′                                                            s                                                k                              )      
The steps of conventional MLL decoding for information block length B and a list size L are as follows:                i. at stage B, rank all path metrics σB(s′, s), and record the L best ones;        ii. for each stage k=B−1, . . . , 1 and for each state s, for all the branches entering s other than the one with largest path metric, i.e.,        
            max                        s          ′                ⁢                              σ            k                    ⁡                      (                                          s                ′                            ,              s                        )                                ⁢        ,rank σk(s′, s) versus the L metrics in the list and keep the L best ones;                iii. find the corresponding L paths, and        iv. check if they pass CRC.        
Once the best L metrics are found, and location recorded, path forward-tracing and back-tracing is performed to identify the corresponding L trellis paths. The Maximum-Log List Algorithm (MLLA) decoder decodes on a full trellis so that path metrics generated from each trellis stage are globally consistent.
In practical modem chipsets, a turbo decoder is implemented with parallel decoding engines. Within each decoding engine, windowing or segmentation of the trellis is applied to reduce memory requirements. By parallelization and segmentation, the full trellis is divided into multiple disjoint or partially overlapping segments, where each segment is initialized independently or using only part of the information provided by the other segments. Consequently, a ranking of σk(s′, s) is not consistent from segment to segment. If the prior art MLLA decoding method is applied to a segmented trellis, the paths selected by the MLLA will not be the most likely ones.
Another disadvantage of the MLLA is that the complexity of searching for L best paths is not fixed. It requires ranking of the path metric at each trellis stage, and insertion of a new path record whenever a new path metric is found to be better than that of any path on the list. As observed, conventional MLLA decoding on an M state trellis, requires at most M sortings of an (L+1) list at each trellis stage, which may be a bottleneck to latency requirements.
A full trellis representation has been used to decode a convolutional code. In practical modem chipsets, turbo decoding is based on a segmented/windowed trellis representation, so that the decoder can decode different segments of the trellis simultaneously. Due to segmentation/windowing of the trellis of a turbo decoder in modem chipsets, the decoder must decode different segments of the trellis simultaneously and without complete information from the other segments. This may result in inconsistent path metrics, and therefore, a selection of candidate codewords based on comparing total accumulated path metrics may fail to identify the most likely paths. The list decoding algorithms of the articles do not provide significant gains for turbo decoding that uses a segmented/windowed trellis. Another disadvantage of conventional decoders is that maintaining a global list of the most likely codewords increases sorting complexity.